// https://www.lintcode.com/problem/best-time-to-buy-and-sell-stock/

public class Solution {
    /**
     * @param prices: Given an integer array
     * @return: Maximum profit
     */
    public int maxProfit(int[] prices) {
        // write your code here
        int ret = 0;
        int bp = prices[0];
        for (int i = 1; i < prices.length; ++i) {
            ret = Math.max(ret, prices[i] - bp);
            bp = Math.min(prices[i], bp);
        }
        return ret;
    }
}